package backtracking;

import java.util.*;


public class Permutationsii47 {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Set<String> resultSet = new HashSet<>();
        backtracing(result, nums, resultSet, 0);
        return result;
    }

    private void backtracing(List<List<Integer>> result, int[] nums, Set<String> resultSet, int index) {
        if (index == nums.length - 1) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < nums.length; i++) {
                sb.append(nums[i]);
            }
            if(resultSet.contains(sb.toString())){
                return;
            }else {
                resultSet.add(sb.toString());
            }
            List<Integer> cur = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                cur.add(nums[i]);
            }
            result.add(cur);
            return;
        }
        for (int i = index; i < nums.length; i++) {
            int temp = nums[index];
            nums[index] = nums[i];
            nums[i] = temp;
            backtracing(result, nums, resultSet, index+1);
            temp = nums[index];
            nums[index] = nums[i];
            nums[i] = temp;
        }

    }


}
